﻿#include "binarysorttree.h"
#include <time.h>
#include <qdebug.h>
#include <stdlib.h>


//root指向双亲结点,初始值是NULL
//当T==NULL时，*p指向根节点，返回false
//当查找成功，*p指向该结点，放回true
//当小于当前结点的值，比较左孩子结点
//当大于当前结点的值，比较有孩子结点
bool search(PBSTree T, int key, PBSTree root, PBSTree *p)
{
    if(T==NULL){
        *p=root;
        return false;
    }
    else if(key == T->data){
        *p=T;
        return true;
    }
    else if(key < T->data)
        return search(T->left,key,T,p);
    else
        return search(T->right,key,T,p);
}
//二叉排序树不允许同时存在两个相同的值
bool insert(PBSTree *T, int data)
{
    PBSTree p=NULL;
    if(false==search(*T,data,NULL,&p)){
        BSTNode* newNode=(BSTNode*)malloc(sizeof(BSTNode));
        if(newNode==NULL)
            return false;
        newNode->data=data;
        newNode->left=NULL;
        newNode->right=NULL;

        if(p==NULL)
            (*T)=newNode;
        else if(data < p->data)
            p->left=newNode;
        else
            p->right=newNode;

        return true;
    }
    else
        return false;
}
#if 0
bool deleteNodeByKey(PBSTree T, const int &key)
{
    if(T==NULL)
        return false;
    if(key==T->data)
        deleteNode(&T);
    else if(key<T->data)
        deleteNodeByKey(T->left,key);
    else if(key>T->data)
        deleteNodeByKey(T->right,key);
}

bool deleteNode(PBSTree *p)
{
    if(*p==NULL)
        return false;
    if((*p)->left==NULL){   //如果左子树为空，连接右子树
        PBSTree tmpNode=*p;
        //        (*p)=(*p)->right;
        (*p)=NULL;
        free(tmpNode);
        tmpNode=NULL;
    }else if((*p)->right==NULL){  //如果右子树为空，连接左子树
        PBSTree tmpNode=*p;
        (*p)=(*p)->left;
        free(tmpNode);
        tmpNode=NULL;
    }else{         //左右子树均不为空
        PBSTree tmpNode=(*p);
        PBSTree s=(*p)->left;//左转，再向右走到尽头。寻找被删结点的前驱。
        while(s->right!=NULL){
            tmpNode=s;
            s=s->right;
        }
        //将被删结点的前驱的值赋值给被删结点。
        (*p)->data=s->data;
        if(tmpNode!=(*p))           //执行过while循环。
            //连接右子树。将前驱的左子树作为前驱父节点的右子树。
            tmpNode->right=s->left;
        else
            //未执行while循环。说明前驱结点没有右子树，连接左子树到前驱父节点的左子树结点。
            tmpNode->left=s->left;

        free(s);
        s=NULL;
    }
    return true;
}
#endif
void Destroy(PBSTree *T)
{
    int num=0;
    Destroy_count(T,&num);
    qDebug()<<("销毁了二叉树结点数：")<<num;
}

void BinarySortTreeNodeTest()
{
    qDebug()<<"----二叉排序树测试函数----";

#if 1
    srand(time(NULL));

    PBSTree T=NULL;

    int data=0;
    printf("array:");
    for(int i=0;i<10;++i){
        data=rand()%100;
        printf("%d ",data);
        insert(&T,data);
    }
    printf("\n");
#endif


    //    //前序遍历
    //    printf("PreOrder:");
    //    preOrder(T);
    //    printf("\n");

    //后序遍历
    printf("PostorderTraverse:");
    PostorderTraverse(T);
    printf("\n");

    qDebug()<<"节点总数:"<<NodeCount(T);
    PrintPBSTree(T);

    qDebug()<<"----测试查找结点函数----";
    PBSTree node=(PBSTree)malloc(sizeof(BSTNode));
    bool searchRe=search(T,data,NULL,&node);
    if(searchRe)
        qDebug()<<"查找成功。"<<node->data;
    else
        qDebug()<<"查找失败。";

    qDebug()<<"----测试删除结点函数----";

    delBST(T,data);

    qDebug()<<"节点总数:"<<NodeCount(T);
    PrintPBSTree(T);

    //
    int count=0;
    Destroy_count(&T,&count);
    qDebug()<<"销毁的结点个数："<<count;
    qDebug()<<"----二叉排序树测试函数结束----";
}

#if 1
//二叉树打印
void PrintPBSTree(PBSTree T)
{
    if(T==NULL){
        qDebug()   <<"二叉树为空。";
        return;
    }
    qDebug()<<"----打印二叉排序树---------------------------------------------------------";
    PrintPBSTreeSub(T,2);
    qDebug()<<"-----------------------------------------------------------------------";
}
//循环打印所有层的数据

void PrintPBSTreeSub(PBSTree t,int h){
    char bra[]={"-/\\<"};
    int i;
    if(t!=NULL){
        PrintPBSTreeSub(t->right,h+1);
        for(i=0;i<h;i++)putchar('\t');
        printf("%d ",t->data);

        putchar(bra[
                ((NULL!=(t->left))<<1)
                |(NULL!=(t->right))
                ]);
        putchar('\n');
        PrintPBSTreeSub(t->left,h+1);
    }
}
#endif

int NodeCount(PBSTree T)
{
    if(T==NULL)
        return 0;
    return 1+NodeCount(T->left)+NodeCount(T->right);
}

void Destroy_count(PBSTree *T, int *count)
{
    if((*T)==NULL)
        return;
    if((*T)->left!=NULL)
        Destroy_count(&((*T)->left),count);
    if((*T)->right!=NULL)
        Destroy_count(&((*T)->right),count);

    free(*T);
    (*T)=NULL;
    ++(*count);
}


BSTNode  * delBST(PBSTree t, int  k)
{
    BSTNode  *p, *f,*s ,*q;
    p=t;
    f=NULL;
    while(p)  /*查找关键字为k的待删结点p*/
    {
        if(p->data==k )  break;  /*找到则跳出循环*/
        f=p;   /*f指向p结点的双亲结点*/
        if(p->data>k)
            p=p->left;
        else
            p=p->right;
    }
    if(p==NULL)  return t;  /*若找不到，返回原来的二叉排序树*/
    if(p->left==NULL)  /*p无左子树*/
    {
        if(f==NULL)//父节点不存在
            t=p->right;  /*p是原二叉排序树的根*/
        else
            if(f->left==p)  /*p是f的左孩子*/
                f->left=p->right ;  /*将p的右子树链到f的左链上*/
            else  /*p是f的右孩子*/
                f->right=p->right ;  /*将p的右子树链到f的右链上*/
        free(p);  /*释放被删除的结点p*/
    }
    else  /*p有左子树*/
    {
        q=p;
        s=p->left;
        while(s->right)  /*在p的左子树中查找最右下结点*/
        {
            q=s;
            s=s->right;
        }
        if(q==p)
            q->left=s->left ;  /*将s的左子树链到q上*/
        else
            q->right=s->left;
        p->data=s->data;  /*将s的值赋给p*/
        free(s);
    }
    return t;
}  /*DelBST*/


//1 当同一个组数据，输入顺序不同构建的二叉排序树相同吗？
void TwoTreeCompare()
{
    qDebug()<<"//1 当同一个组数据，输入顺序不同构建的二叉排序树相同吗？";
    //数组某几位移动到数组后面
    int array[10]={34,65,63,76,89,21,33,44,78,92};
    int newArray[10]={33,44,78,92,34,65,63,76,89,21};

    PBSTree tree1=NULL;
    PBSTree tree2=NULL;

    for(int i=0;i<10;++i){
        insert(&tree1,array[i]);
        insert(&tree2,newArray[i]);
    }

    PrintPBSTree(tree1);
    PrintPBSTree(tree2);
}
//2 将一个二叉树转化成二叉排序树
void conversion()
{

}

#if 0
//非递归
//非递归也是一个基于递归的思想：
//左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，
right部分的最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看右子树是否符合条件即可，
//即使到达了左子树，左子树也可以看出由左右子树组成的树还想右子树那样处理.

//对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
//只需看看右子树的右子树是否符合要求即可
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size = sequence.size();
        if(0==size)return false;

        int i = 0;
        while(--size)
        {
            while(sequence[i++]<sequence[size]);
            while(sequence[i++]>sequence[size]);

            if(i<size)return false;
            i=0;
        }
        return true;
    }
};
#endif


vector<int> preorderTraverse(BSTNode *root)
{
    static vector<int> reVtr;
    if(root==NULL)
        return reVtr;

    reVtr.push_back(root->data);
    printf("%d ",root->data);

    preorderTraverse(root->left);
    preorderTraverse(root->right);
}

vector<int> InorderTraverse(BSTNode *root)
{
    static vector<int> reVtr;
    if(root==NULL)
        return reVtr;

    InorderTraverse(root->left);

    reVtr.push_back(root->data);
    printf("%d ",root->data);

    InorderTraverse(root->right);
}

vector<int> PostorderTraverse(BSTNode *root)
{
    static vector<int> reVtr;
    if(root==NULL)
        return reVtr;

    PostorderTraverseSub(root,&reVtr);

    return reVtr;
}

void CreateBSTree(BSTNode **root, const int count)
{
    vector<int>intVtr;
    vector<int>::iterator it;
    srand(time(NULL));
    for(int i=0;i<count;++i){
        int data=rand()%100;
        it=find(intVtr.begin(),intVtr.end(),data);
        if(it==intVtr.end())//无重复
            intVtr.push_back(data);
        else    //重复，忽略该数字，索引补偿。
            --i;
    }

    qDebug()<<"创建二叉排序树，模拟前序遍历数据：";
    for(auto &i:intVtr){
        printf("%d ",i);
        insert(root,i);
    }
    printf("\n");

    //打印二叉排序树
    PrintPBSTree(*root);
}

void Q3_VerifySquenceOfBSTTest()
{
    //测试1
    BSTNode *root=NULL;
    CreateBSTree(&root,10);

    qDebug()<<"二叉排序树后序遍历：";
    vector<int>re=PostorderTraverse(root);
    printf("\n");

    printf("re:");
    for(auto&i:re)
        printf("%d-",i);
    printf("\n");

    if(Q3_VerifySquenceOfBST(re))
        qDebug()<<"函数测试通过。";
    else
        qDebug()<<"函数测试不通过。";
#if 0
    //测试2
    re.clear();
    BSTNode *root2=NULL;
    CreateBSTree(&root2,10);

    qDebug()<<"二叉排序树后序遍历：";
    re=PostorderTraverse(root2);
    printf("\n");

    if(Q3_VerifySquenceOfBST(re))
        qDebug()<<"函数测试通过。";
    else
        qDebug()<<"函数测试不通过。";
    //测试3
    re.clear();
    BSTNode *root3=NULL;
    CreateBSTree(&root3,10);

    qDebug()<<"二叉排序树后序遍历：";
    re=PostorderTraverse(root3);
    printf("\n");

    if(Q3_VerifySquenceOfBST(re))
        qDebug()<<"函数测试通过。";
    else
        qDebug()<<"函数测试不通过。";
#endif
    Destroy(&root);
    //    destroy(&root2);
    //    destroy(&root3);
}

bool Q3_VerifySquenceOfBST(const vector<int> &intVtr)
{
    if(intVtr.size()==0)
        return false;
    size_t size=intVtr.size();
    int i=0;

    while(--size){
        //        printf("%d-",size);
        while(intVtr[i++]<intVtr[size]);
        while(intVtr[i++]>intVtr[size]);
        if(i<size)
            return false;
        i=0;
    }
    return true;
}

void PostorderTraverseSub(BSTNode *root, vector<int> *intVtr)
{
    if(root!=NULL){
        PostorderTraverseSub(root->left,intVtr);
        PostorderTraverseSub(root->right,intVtr);

        printf("%d ",root->data);
        intVtr->push_back(root->data);
    }
}

void Q4_ConvertTest()
{
    BSTNode *root=NULL;
    CreateBSTree(&root,10);

    BSTNode *pDoubleListHead=Q4_Convert(root);
    //遍历双线链表输出
    BSTNode *cur=pDoubleListHead;
    printf("Traverse right:");
    while(cur!=NULL){
        printf("%d ",cur->data);
        cur=cur->right;
    }
    printf("\n");

    //逆向遍历输出
    printf("Traverse left:");
    while(cur!=NULL){
        printf("%d ",cur->data);
        cur=cur->left;
    }
    printf("\n");

    //销毁链表
    int count=0;
   while(cur!=NULL) {
       BSTNode *tmp=cur;
       cur=cur->right;
       delete tmp;
       tmp=NULL;
       ++count;
   }
   qDebug()<<"销毁了链表结点个数："<<count;

 //   Destroy(&root);
}


void Q4_ConvertRecursion(BSTNode *root, BSTNode *pre)
{
    if(root==NULL)
        return  ;

    Q4_ConvertRecursion(root->left,pre);

    root->left=pre;
    if(pre!=NULL)
        pre->right=root;
    pre=root;

    Q4_ConvertRecursion(root->right,pre);
}

BSTNode *Q4_Convert(BSTNode *root)
{
    if(root==NULL)
        return NULL;
    BSTNode *preNode=NULL;
    Q4_ConvertRecursion(root,preNode);

//    if(root!=NULL)
//        while(root->left!=NULL)
//            root=root->left;

//    return root;
    BSTNode *re=root;
    if(re!=NULL)
        while(re->left!=NULL)
            re=re->left;
    return re;
}
